#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

 

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例  2:

输入：word1 = "leetcode", word2 = "etco"
输出：4
 

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-operation-for-two-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*
 * */
//todo 这个题没想起来 光看dp了没看懂 然后看了一个视频 说一个思路是求这俩公共序列 然后这俩长度减去公共序列*2 =需要删除的
int minDistance(string word1, string word2) {

    int maxV=0;
    vector<vector<int>>  dp(word1.size()+1,vector<int>(word2.size()+1,0));

    //这个查找重复数组的写错了
    for (int i = 1; i <=word1.size() ; ++i) {

        for (int j = 1; j <=word2.size() ; ++j) {

            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }

            maxV=max(maxV,dp[i][j]);

        }


    }

    int ret=word1.size()+word2.size()-(2*maxV);

    if(ret<=0)
        return 0;


    return ret;
}


//int minDistance(string word1, string word2) {
//
//    int maxV=0;
//    vector<vector<int>>  dp(word1.size()+1,vector<int>(word2.size()+1,0));
//
//    //这个查找重复数组的写错了
//    for (int i = 0; i <word1 .size(); ++i) {
//        if (word1[i]==word2[0])
//            dp[i][0]=1;
//        else if (i-1>=0)
//            dp[i][0]= max(dp[i-1][0],0);
//
//        maxV= max(maxV, dp[i][0]);
//    }
//
//    for (int i = 0; i <word2 .size(); ++i) {
//
//        if (word1[0]==word2[i])
//            dp[0][i]=1;
//        else if (i-1>=0)
//            dp[0][i]= max(dp[0][i-1],0);
//
//        maxV= max(maxV, dp[0][i]);
//    }
//
//
//    for (int i = 1; i <word1 .size() ; ++i) {
//        for (int j = 1; j <word2 .size() ; ++j) {
//            if (word1[i]==word2[j])
//                dp[i][j]=dp[i-1][j-1]+1;
//            else
//                dp[i][j]= max(dp[i-1][j],dp[i][j-1]);
//
//            maxV= max(maxV,dp[i][j]);
//        }
//    }
//
//    int ret=word1.size()+word2.size()-(2*maxV);
//
//    if(ret<=0)
//        return 0;
//
//
//    return ret;
//}